The Saint-Exupéry Ruler

puzzle
modeling

Problem description

Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away.
— Antoine de Saint-Exupéry

The problem is to design a ruler of \(n\) units using the fewest possible graduations, such that all possible integer lengths appear on the ruler. This puzzle was published by Mickaël Launay (Launay 2025). An example with \(n=6\) is displayed in the Figure below:

Illustration from (Launay 2025)

Length \(1\) can be measured with marks \(0\) and \(1\), length \(2\) with marks \(4\) and \(6\), length \(3\) with marks \(1\) and \(4\), length \(4\) with marks \(0\) and \(4\), length \(5\) with marks \(6\) and \(1\), and length \(6\) with marks \(0\) and \(6\).

MIP model

Parameters

  • \(N = \{0,1,\dots,n\}\): set of units of the ruler

Variables

  • \(\textcolor{blue}{x}_i \in \{0,1\}\): takes value \(1\) if and only if there is a mark on unit \(i\in N\)
  • \(\textcolor{blue}{y}_{i,j} \in \{0,1\}\): takes value \(1\) if and only if there are marks on units \(i\in N\) and \(j\in N\), \(i< j\)

Objective function

The problem is to minimize the number of marks:

\[ \min \sum_{i \in N} \textcolor{blue}{x}_i \]

subject to:

Constraints

  • All possible integer lengths must appear somehow on the ruler:

\[ \sum_{i<j, \;j-i=k} \textcolor{blue}{y}_{i,j} \ge 1 \quad \forall k \in N, k>0 \tag{1} \]

  • Variables \(\textcolor{blue}{x}_i\) and \(\textcolor{blue}{y}_{i,j}\) must be consistent:

\[\begin{align} \textcolor{blue}{y}_{i,j} &\le \textcolor{blue}{x}_i &\forall i<j \tag{2}\\ \textcolor{blue}{y}_{i,j} &\le \textcolor{blue}{x}_j &\forall i<j \tag{3}\\ \textcolor{blue}{x}_i+\textcolor{blue}{x}_j &\le \textcolor{blue}{y}_{i,j}+1 &\forall i<j \tag{4} \\ \end{align}\]

Constraints \((2)\) and \((3)\) enforce \(\textcolor{blue}{y}_{i,j}=1\implies \textcolor{blue}{x}_i=1\) and \(\textcolor{blue}{x}_j=1\), constraints \((4)\) enforce the reciprocal relationship.

Solution

Solving this problem with \(n=20\) takes less than a second with the default solver in PuLP (CBC) and yields:

So the 20 unit ruler can be designed with \(8\) marks. We can check that all integer lengths do appear on the ruler (some lengths appear multiple times):

length -> endpoints
-------------------
1 -> 1 0
1 -> 19 18
1 -> 20 19
2 -> 6 4
2 -> 20 18
3 -> 4 1
4 -> 4 0
5 -> 6 1
5 -> 11 6
6 -> 6 0
7 -> 11 4
7 -> 18 11
8 -> 19 11
9 -> 20 11
10 -> 11 1
11 -> 11 0
12 -> 18 6
13 -> 19 6
14 -> 18 4
14 -> 20 6
15 -> 19 4
16 -> 20 4
17 -> 18 1
18 -> 18 0
18 -> 19 1
19 -> 19 0
19 -> 20 1
20 -> 20 0
Source: Saint‑Exupéry ruler

References

Launay, Mickaël. 2025. “La Règle Saint-Exupérienne : L’énigme Maths Du Monde n°82.” 2025. https://www.lemonde.fr/sciences/article/2025/12/20/la-regle-saint-exuperienne-l-enigme-maths-du-monde-n-82_6658931_1650684.html.